package com.interview.javabase.algorithm.动态规划;

import java.util.Arrays;

/**
 * @author www.byteblogs.com
 * @date 2021-10-07
 * @since 2.0
 */
public class 最大子数组问题 {

    public static void main(String[] args) {
        int[] arr = new int[]{-3, 1, 3, -1, 2, -4, 2};
        System.out.println("maxSubArray(arr) = " + maxSubArray(arr));
    }

    static int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];

        Arrays.fill(dp, 0);
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }

        int result = 0;
        for (int i = 0; i < dp.length; i++) {
            result = Math.max(result, dp[i]);
        }

        return result;
    }
}
